1062E - Company - CodeForces Solution

// [ нvмegy ]
// OLPCHUYENTIN2023 GOTOHUE
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(c) c.begin(), c.end()
#ifdef hvmegy
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
	cerr << "[" << vars << " : ";
	string delim = "";
	(..., (cerr << delim << values, delim = ", "));
	cerr << "]" << '\n'; 
}
#else
#define dbg(...)
#endif

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int GOTOHUE();

int32_t main()
{
        cin.tie(0) -> sync_with_stdio(0); 
        cout << fixed << setprecision(15);
	#ifdef hvmegy
		freopen("input.txt", "r", stdin); 
		freopen("output.txt", "w", stdout); 
		freopen("log.txt", "w", stderr);
	#endif
        bool MULTITEST = 0; 
        int OLPCHUYENTIN2023 = 1; 
        if (MULTITEST) cin >> OLPCHUYENTIN2023; 
	for (int i = 1; i <= OLPCHUYENTIN2023; i++) {
		if (GOTOHUE()) break;
		#ifdef hvmegy
			cout << "--ENDTEST--" << '\n';
		#endif
	}
	#ifdef hvmegy
		cerr << '\n' << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << '\n';
	#endif
        return 0;
}

int const N = 1e5 + 1; 
int n, numq; 
vector<int> adj[N]; 
int in[N], out[N], d[N], par[N][20], mn[N][20], mx[N][20], lca[N][20]; 
int cur = 0; 

void dfs(int u) { 
	in[u] = ++cur; 
	for (int v : adj[u]) { 
		d[v] = d[u] + 1;
		dfs(v); 
	}
	out[u] = cur; 
}

int LCA(int u, int v) { 
	if (d[u] < d[v]) swap(u, v);
	int det = d[u] - d[v]; 
	for (int i = 18; i >= 0; i--) { 
		if ((det >> i) & 1LL) { 
			u = par[u][i]; 
		}
	}
	if (u == v) { 
		return v; 
	}
	for (int i = 18; i >= 0; i--) { 
		if (par[u][i] != par[v][i]) { 
			u = par[u][i]; 
			v = par[v][i]; 
		}
	}
	return par[u][0]; 
}
int lcaseg(int l, int r) { 
	int len = __lg(r - l + 1); 
	return LCA(lca[l][len], lca[r-(1 << (len))+1][len]); 
}

int GOTOHUE() {
	cin >> n >> numq; 
	for (int i = 2; i <= n; i++) { 
		int p; 
		cin >> p; 
		par[i][0] = p; 
		adj[p].push_back(i); 
	}
	dfs(1); 
	par[1][0] = 1; 
	for (int i = 1; i <= 18; i++) { 
		for (int u = 1; u <= n; u++) { 
			par[u][i] = par[par[u][i-1]][i-1]; 
		}
	}
	for (int i = 1; i <= n; i++) { 
		lca[i][0] = mn[i][0] = mx[i][0] = i; 
	}
	for (int i = 1; i <= 18; i++) { 
		for (int j = 1; (j + (1 << i) - 1) <= n; j++) { 
			mn[j][i] = (in[mn[j][i-1]] < in[mn[j + (1 << (i-1))][i-1]] ? mn[j][i-1] : mn[j + (1 << (i-1))][i-1]);
			mx[j][i] = (in[mx[j][i-1]] > in[mx[j + (1 << (i-1))][i-1]] ? mx[j][i-1] : mx[j + (1 << (i-1))][i-1]);
			lca[j][i] = LCA(lca[j][i-1], lca[j + (1 << (i-1))][i-1]); 
		}
	}
	cerr << '\n';

	while (numq--) { 
		int l, r; 
		cin >> l >> r; 
		int len = __lg(r - l + 1); 
		int getmn = (in[mn[l][len]] < in[mn[r - (1 << (len)) + 1][len]] ? mn[l][len] : mn[r - (1 << (len)) + 1][len]); 
		int getmx = (in[mx[l][len]] > in[mx[r - (1 << (len)) + 1][len]] ? mx[l][len] : mx[r - (1 << (len)) + 1][len]); 
		int lca1, lca2; 
		if (getmn == l) lca1 = lcaseg(getmn + 1, r); 
		else if (getmn == r) lca1 = lcaseg(l, getmn-1); 
		else lca1 = LCA(lcaseg(l, getmn-1), lcaseg(getmn+1, r)); 

		if (getmx == l) lca2 = lcaseg(getmx + 1, r); 
		else if (getmx == r) lca2 = lcaseg(l, getmx-1); 
		else lca2 = LCA(lcaseg(l, getmx-1), lcaseg(getmx+1, r));

		if (d[lca1] > d[lca2]) { 
			cout << getmn << " " << d[lca1] << '\n';
		}
		else { 
			cout << getmx << " " << d[lca2]<< '\n';
		}
	}
	


	return 0;
}